home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Linux Cubed Series 7: Sunsite
/
Linux Cubed Series 7 - Sunsite Vol 1.iso
/
system
/
filesyst
/
dosfs
/
dmsdosfs.000
/
dmsdosfs
/
dmsdosfs-0.6.9b
/
dmsdos_compr.c
< prev
next >
Wrap
C/C++ Source or Header
|
1996-07-29
|
14KB
|
484 lines
/*
linux/fs/dmsdos/dmsdos_compr.c
DMSDOS filesystem: compression routines
******************************************************************************
DMSDOS (Doublespace/Drivespace compressed MSDOS filesystem) for Linux
written 1995,1996 by Frank Gockel
(C) Copyright 1995,1996 by Frank Gockel
Some code of the dmsdos filesystem has been copied from the msdos filesystem
so there are the following additional copyrights:
(C) Copyright 1992,1993 by Werner Almesberger (msdos filesystem)
(C) Copyright 1994,1995 by Jacques Gelinas (mmap code)
(C) Copyright 1992-1995 by Linus Torvalds
The DMSDOS filesystem was inspired by the THS filesystem (a simple doublespace
DS-0-2 compressed read-only filesystem) written 1994 by Thomas Scheuermann.
The DMSDOS filesystem is distributed under the Gnu General Public Licence.
See file COPYING for details.
******************************************************************************
*/
#include <linux/errno.h>
#include <linux/kernel.h>
#include <linux/malloc.h>
#include <linux/fs.h>
#include <linux/msdos_fs.h>
#include <linux/dmsdos_fs.h>
/* undef this to avoid compression */
#define DBL_COMPRESSION
/* GUESS_HACK forces the compression scheme guessing code to return JM-0-1 as
result when it in fact has guessed SQ-0-0. This is because SQ-0-0 is
currently unsupported, so write access would be always uncompressed on
SQ-0-0 compressed drives. 'undef' this to avoid this hack */
#define GUESS_HACK
#ifdef __KERNEL__
extern Dblsb dblsb[];
#else
extern int cfaktor;
void panic(char*);
#endif /*__KERNEL__*/
/* maybe the values have to be adapted for optimal compression/speed
relationship */
int c_maxdiff[12]={ 63, 63, 63, 63,319,319,319,319,4414,4414,4414,4414};
int c_maxlen[12] ={ 64,128,256,512, 64,128,256,512, 64, 128, 256, 512};
inline void putbit(unsigned char*clusterk,int*zielpos,int*zielmask,int bit)
{
if(bit)clusterk[*zielpos]|=*zielmask;
else clusterk[*zielpos]&=~(*zielmask);
(*zielmask)<<=1;
if(*zielmask==256)
{ *zielmask=1;
++(*zielpos);
}
}
void putbits(unsigned char*clusterk,int*zielpos,int*zielmask,int byte,int anz)
{ int i;
int mask;
mask=1;
for(i=0;i<anz;++i)
{ putbit(clusterk,zielpos,zielmask,byte&mask);
mask<<=1;
}
}
void write_byte(unsigned char*clusterk,int*zielpos,int*zielmask,int byte,
int method)
{ if(method!=JM_0_0&&method!=JM_0_1)
{ if(byte<128)putbits(clusterk,zielpos,zielmask,2,2);
else putbits(clusterk,zielpos,zielmask,1,2);
}
else /* JM_0_0 */
{ if(byte<128)putbit(clusterk,zielpos,zielmask,0);
else putbits(clusterk,zielpos,zielmask,3,2);
}
putbits(clusterk,zielpos,zielmask,byte,7);
}
void write_temp(unsigned char*clusterk,int*zielpos,int*zielmask,
unsigned char*tempstr,int len,int diff,int method)
{ if(len==1)
{ write_byte(clusterk,zielpos,zielmask,tempstr[0],method);
return;
}
if(len==2&&(method==JM_0_0||method==JM_0_1))
{ write_byte(clusterk,zielpos,zielmask,tempstr[0],method);
write_byte(clusterk,zielpos,zielmask,tempstr[1],method);
return;
}
if(method!=JM_0_0&&method!=JM_0_1)
{ ++len; /* corrects different counting scheme */
if(diff<64)putbits(clusterk,zielpos,zielmask,0,2);
else putbits(clusterk,zielpos,zielmask,3,2);
}
else /* JM_0_0 */
{ putbits(clusterk,zielpos,zielmask,1,2);
putbit(clusterk,zielpos,zielmask,(diff<64)?0:1);
}
if(diff<64)putbits(clusterk,zielpos,zielmask,diff,6);
else
{ if(diff<320)
{ putbit(clusterk,zielpos,zielmask,0);
putbits(clusterk,zielpos,zielmask,diff-64,8);
}
else
{ putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,diff-320,12);
}
}
/* okay, now encode len */
if(len==3)
{ putbit(clusterk,zielpos,zielmask,1);
return;
}
putbit(clusterk,zielpos,zielmask,0);
if(len<6)
{ putbit(clusterk,zielpos,zielmask,1);
putbit(clusterk,zielpos,zielmask,len-4);
return;
}
putbit(clusterk,zielpos,zielmask,0);
if(len<10)
{ putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,len-6,2);
return;
}
putbit(clusterk,zielpos,zielmask,0);
if(len<18)
{ putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,len-10,3);
return;
}
putbit(clusterk,zielpos,zielmask,0);
if(len<34)
{ putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,len-18,4);
return;
}
putbit(clusterk,zielpos,zielmask,0);
if(len<66)
{ putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,len-34,5);
return;
}
putbit(clusterk,zielpos,zielmask,0);
if(len<130)
{ putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,len-66,6);
return;
}
putbit(clusterk,zielpos,zielmask,0);
if(len<258)
{ putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,len-130,7);
return;
}
putbit(clusterk,zielpos,zielmask,0);
putbit(clusterk,zielpos,zielmask,1);
putbits(clusterk,zielpos,zielmask,len-258,8);
}
void write_marker(unsigned char*clusterk,int*zielpos,int*zielmask,int method)
{ if(method==JM_0_0||method==JM_0_1)putbits(clusterk,zielpos,zielmask,13,4);
else /* DS_0_x */ putbits(clusterk,zielpos,zielmask,7,3);
putbits(clusterk,zielpos,zielmask,0xFFF,12);
}
inline int such_rb_byte(unsigned char*clusterd, int byte, int ab)
{ while(ab>=0)
{ if(byte==clusterd[ab])return ab;
--ab;
}
return -1;
}
inline int mystrncmp(unsigned char*a,unsigned char*b,int len)
{ --len;
while(len>=0)
{ if(a[len]!=b[len])return 1;
--len;
}
return 0;
}
inline int such_rb_string(unsigned char*clusterd,unsigned char*tempstr,int ab,
int len)
{ while(ab>=0)
{ if(mystrncmp(tempstr,&(clusterd[ab]),len)==0)return ab;
--ab;
}
return -1;
}
/* compresses a cluster
gets uncompressed size (number of used sectors)
returns compressed size (in number of used sectors) or -1 if failed
*/
int compress(unsigned char* clusterk, unsigned char* clusterd, int size,
int method,int cvfnr)
{
#ifdef DBL_COMPRESSION
int i;
int j;
int zielpos;
int zielmask;
int pos;
int lentemp;
int maxzielpos;
int byte;
int rb_pos=0; /* avoids warning */
int rb_beg=0; /* avoids warning */
int last_rb_pos;
#ifdef __KERNEL__
int maxdiff=c_maxdiff[dblsb[cvfnr].s_cfaktor];
int maxlen=c_maxlen[dblsb[cvfnr].s_cfaktor];
#else
int maxdiff=c_maxdiff[cfaktor];
int maxlen=c_maxlen[cfaktor];
#endif /*__KERNEL__*/
switch(method)
{ case DS_0_0:
case DS_0_1:
case DS_0_2: /* handled together with JM_0_0 because similar */
case JM_0_0:
case JM_0_1:
zielpos=0;
zielmask=1;
pos=0;
lentemp=0;
maxzielpos=(size-1)*512;
/* put magic number */
putbits(clusterk,&zielpos,&zielmask,method,32);
for(i=0;i<size;++i)
{ for(j=0;j<512;++j)
{ byte=clusterd[i*512+j];
/* begin compression algorithm (sorry for using gotos...) */
retry:
if(pos==0) /* hmm... first byte, nothing to compress */
{ write_byte(clusterk,&zielpos,&zielmask,byte,method);
++pos;
goto end;
}
if(lentemp==0)
{ rb_pos=such_rb_byte(clusterd,byte,pos-1);
if(rb_pos<0||pos-rb_pos>maxdiff)
{ write_byte(clusterk,&zielpos,&zielmask,byte,method);
++pos;
goto end;
}
rb_beg=pos;
lentemp=1;
++pos;
goto end;
}
else
{ ++lentemp;
if(lentemp+rb_pos>rb_beg) goto norb;
if(byte!=clusterd[rb_pos+lentemp-1]) goto norb;
if(lentemp==maxlen)
{ write_temp(clusterk,&zielpos,&zielmask,&(clusterd[rb_beg]),
lentemp,rb_beg-rb_pos,method);
lentemp=0;
}
++pos;
goto end;
norb:
last_rb_pos=rb_pos;
rb_pos=such_rb_string(clusterd,&(clusterd[rb_beg]),
rb_beg-lentemp,lentemp);
if(rb_pos<0||rb_beg-rb_pos>maxdiff)
{ --lentemp;
write_temp(clusterk,&zielpos,&zielmask,&(clusterd[rb_beg]),
lentemp,rb_beg-last_rb_pos,method);
lentemp=0;
goto retry;
}
++pos;
}
/* end compression algorithm */
end:
if(zielpos>maxzielpos)return -1; /* incompressible data */
}
if(lentemp>0)
{ write_temp(clusterk,&zielpos,&zielmask,&(clusterd[rb_beg]),
lentemp,rb_beg-rb_pos,method);
lentemp=0;
}
write_marker(clusterk,&zielpos,&zielmask,method);
}
if(zielpos>maxzielpos)return -1;
if(zielmask!=1)++zielpos; /* last byte is only used if mask != 1 */
return (zielpos-1)/512+1;
default:
/* sorry, other compression methods currently not available */
return -1;
}
#endif
return -1;
}
/* write a dmsdos cluster, compress before if possible;
length is the number of used bytes, may be < SECTOR_SIZE*sectperclust only
in the last cluster of a file;
cluster must be allocated by allocate_cluster before if it is a new one;
unable to write dir clusters;
to avoid MDFAT level fragmentation, near_sector should be the sector no
of the preceeding cluster;
if ucflag>0 uncompressed write is forced (only for umsdos --linux-.---)
if ucflag<0 raw write is forced with compressed size -ucflag (in sectors).
*/
#ifdef __KERNEL__
int dmsdos_write_cluster(struct super_block*sb,
unsigned char* clusterd, int length, int clusternr,
int near_sector, int cvfnr, int ucflag)
{ int method;
unsigned char* clusterk;
int size;
Mdfat_entry mde;
int sektor;
int i;
int res;
int ksize;
struct buffer_head*bh;
LOCK_READWRITE;
/*printk("DMSDOS write_cluster clusternr=%d length=%d near_sector=%d cvfnr=%d\n",
clusternr,length,near_sector,cvfnr);*/
/* guess compression method if not already known */
if(dblsb[cvfnr].s_comp==GUESS)
{
printk("DMSDOS: write_cluster: guessing compression method...\n");
for(i=2;i<=dblsb[cvfnr].s_max_cluster;++i)
{ dbl_mdfat_value(sb,i,cvfnr,NULL,&mde);
/*if((mdfat&0xC0000000)==0x80000000)*/
if(mde.flags==2)
{ bh=read_dbl_sector(sb,mde.sector_minus_1+1,cvfnr);
if(bh!=NULL)
{
res=CHL(bh->b_data);
bh_free(sb,bh);
if(res==DS_0_0){dblsb[cvfnr].s_comp=DS_0_0;goto guess_ok;}
if(res==DS_0_1){dblsb[cvfnr].s_comp=DS_0_1;goto guess_ok;}
if(res==DS_0_2){dblsb[cvfnr].s_comp=DS_0_2;goto guess_ok;}
if(res==JM_0_0){dblsb[cvfnr].s_comp=JM_0_0;goto guess_ok;}
if(res==JM_0_1){dblsb[cvfnr].s_comp=JM_0_1;goto guess_ok;}
if(res==SQ_0_0){dblsb[cvfnr].s_comp=SQ_0_0;goto guess_ok;}
}
}
}
printk("DMSDOS: could not guess compression method for CVF %d\n",cvfnr+1);
dblsb[cvfnr].s_comp=UNCOMPRESSED;
guess_ok:
printk("DMSDOS: write_cluster: guessed 0x%08x.\n",dblsb[cvfnr].s_comp);
#ifdef GUESS_HACK
if(dblsb[cvfnr].s_comp==SQ_0_0)
{ dblsb[cvfnr].s_comp=JM_0_1;
printk("DMSDOS: guess_hack: guessed SQ-0-0 not supported, using JM-0-1 instead.\n");
}
#endif
}
method=dblsb[cvfnr].s_comp; /* default compression method */
size=(length-1)/512+1;
if(size==1||ucflag!=0)method=UNCOMPRESSED; /* will not become smaller */
if(method==UNCOMPRESSED) /* includes RAW write */
{ clusterk=clusterd;
if(ucflag<0)
{ /* raw write of already compressed data (for dmsdosd/ioctl) */
ksize=-ucflag;
mde.size_lo_minus_1=ksize-1;
mde.size_hi_minus_1=size-1;
mde.flags=2;
}
else
{ /* normal uncompressed write */
/*mdfat=0xC0000000|((size-1)<<26)|((size-1)<<22);*/
mde.size_lo_minus_1=size-1;
mde.size_hi_minus_1=size-1;
mde.flags=3;
ksize=size;
}
}
else
{ if(try_daemon(clusternr,cvfnr,length,method))goto wr_uc;
clusterk=(unsigned char*)MALLOC(size*SECTOR_SIZE);
if(clusterk==NULL)
{ printk("DMSDOS: write_cluster: no memory for compression, writing uncompressed!\n");
wr_uc:
clusterk=clusterd;
/*mdfat=0xC0000000|((size-1)<<26)|((size-1)<<22);*/
mde.size_lo_minus_1=size-1;
mde.size_hi_minus_1=size-1;
mde.flags=3;
method=UNCOMPRESSED;
ksize=size;
}
else
{ /*printk("DMSDOS: write_cluster: compressing...\n");*/
ksize=compress(clusterk,clusterd,size,method,cvfnr);
/*printk("DMSDOS: write cluster: compressing finished\n");*/
if(ksize<0)
{ /* compression failed */
FREE(clusterk);
clusterk=clusterd;
/*mdfat=0xC0000000|((size-1)<<26)|((size-1)<<22);*/
mde.size_lo_minus_1=size-1;
mde.size_hi_minus_1=size-1;
mde.flags=3;
method=UNCOMPRESSED;
ksize=size;
}
else
{ /*mdfat=0x80000000|((size-1)<<26)|((ksize-1)<<22);*/
mde.size_lo_minus_1=ksize-1;
mde.size_hi_minus_1=size-1;
mde.flags=2;
}
}
}
/*printk("DMSDOS: write_cluster: call replace_existing_cluster mdfat=0x%x\n",
mdfat);*/
sektor=replace_existing_cluster(sb,clusternr,near_sector,&mde,cvfnr);
/*printk("DMSDOS: write_cluster: replace_existing_cluster returned %d\n",
sektor);*/
if(sektor<0)res=-ENOSPC;
else
{ res=0;
for(i=0;i<ksize;++i)
{ bh=noread_dbl_sector(sb,sektor+i,cvfnr);
if(bh==NULL)res=-EIO;
else
{
memcpy(bh->b_data,&(clusterk[SECTOR_SIZE*i]),SECTOR_SIZE);
bh_dirty(sb,bh);
bh_free(sb,bh);
}
}
}
if(method!=UNCOMPRESSED)FREE(clusterk);
UNLOCK_READWRITE;
return res;
}
#endif /*__KERNEL__*/